// GreedyAlgorithm.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <algorithm>
#include "KnapsackProblem.h"
#include "CoinChange.h"
#include "DistributeCookie.h"
#include "NonOverlapSection.h"

using namespace std;

int main()
{
	vector<KnapsackObject> objects = {
		{30, 10, false}, {30, 40, false}, {60, 30, false}, 
		{50, 50, false}, {40, 35, false}, {10, 40, false},
		{25, 30, false}
	};
	Knapsack knapsack = { {}, 0 };

	int total = 150;

	//int num;
	//cin >> num;

	//int weight;
	//for (int i = 0; i < num; i++) {
	//	cin >> weight;
	//	objects.push_back({ weight, 0, false });
	//}

	//int price;
	//for (int i = 0; i < num; i++) {
	//	cin >> price;
	//	objects[i].Price = price;
	//}

	//按重量排序
	std::sort(objects.begin(), objects.end(), CompareKnapsackObjectByWeight);

	int index;
	while ((index = ChooseFuncByUnitPrice(objects, total - knapsack.Total)) != -1) {
		knapsack.Objects.push_back(objects[index]);
		knapsack.Total += objects[index].Weight;
		
	}

	PrintObjects(knapsack.Objects);

	//最少找零
	vector<Coin> coins = {
		{1, 3}, {2, 3}, {5, 2}, {20, 1}, {10, 1}, {50, 3}, {100, 3}
	};
	vector<int> result = CoinChange(446, coins);
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << " ";
	cout << endl;

	//分发饼干 🍪
	vector<int> appetites = { 1, 4 };
	vector<int> sizes = { 1, 2, 3 };
	int distributeCookie = DistibuteCookie(appetites, sizes);
	cout << distributeCookie << endl;

	//不重叠区间
	vector<Section> sections = {
		{1, 2}, {1, 2}, {3, 4}, {1, 3}
	};
	int nonOverlapSection = NonOverlapSection(sections);
	cout << nonOverlapSection << endl;
}
